package com.company.ljh.medium;

import com.company.ljh.utils.ListNode;

/**
 * @description:
 * 328. 奇偶链表
 * 中等
 * 707
 * 相关企业
 * 给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
 *
 * 第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
 *
 * 请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
 *
 * 你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2023/7/4 14:47
 * @version:1.0
 */
public class 奇偶链表 {
    //交替生成链表即可，注意，偶链表最后一个节点置空
    public ListNode oddEvenList(ListNode head) {
        ListNode firstHead = new ListNode();
        ListNode headTemp = head;

        //保留第二个链表头节点方便组装
        ListNode secondtHeadTemp = new ListNode();
        ListNode secondtHead = secondtHeadTemp;
        int i = 1;
        while(head != null){
            if(i % 2 ==1){
                //奇数
                firstHead.next = head;
                firstHead = firstHead.next;
            }else{
                secondtHead.next = head;
                secondtHead = secondtHead.next;
            }

            i++;
            head = head.next;
        }
        firstHead.next = secondtHeadTemp.next;
        //最后一个节点需要将next置为null
        secondtHead.next = null;
        return headTemp;

    }
}
